package binarySearchTree;

public class BinarySearchTree<T> {
	
	protected BinaryNode<T> root;
	
    public BinarySearchTree( ) {
        root = null;  
    } 
    
    public BinaryNode getRoot( ) {
        return root; 
    } 
    
	public void insert( Comparable <T>x ) {
        root = insert( x, root );
    }
    
   
	public void remove( Comparable <T>x ) {
        root = remove( x, root );
    }
    
    public void removeMin( ) {
        root = removeMin( root );
    }
    @SuppressWarnings("unchecked")
    public Comparable findMin( ) {
        return elementAt( findMin( root ) );
    }
    @SuppressWarnings("unchecked")
    public Comparable findMax( ) {
        return elementAt( findMax( root ) );
    }
    @SuppressWarnings("unchecked")
    public Comparable find( Comparable <T>x ) {
        return elementAt( find( x, root ) );
    }
    
    public void makeEmpty( ) {
        root = null;
    }
    
    public boolean isEmpty( ) {
        return root == null;
    }
    
    private Comparable<T> elementAt( BinaryNode <T>t ) {
        return t == null ? null : t.element;
    }
    @SuppressWarnings("unchecked")
    protected BinaryNode<T> insert( Comparable <T>x, BinaryNode <T>t ) {
        if( t == null )
            t = new BinaryNode<T>( x );
        else if( x.compareTo( (T) t.element ) <= 0 )
            t.setLeft(insert( x, t.getLeft() ));
        else if( x.compareTo( (T) t.element ) > 0 )
            t.right = insert( x, t.right );
        else
            throw new DuplicateItemException( x.toString( ) );  
        return t;
    }
    @SuppressWarnings("unchecked")
    protected BinaryNode<T> remove( Comparable <T>x, BinaryNode <T>t ) {
        if( t == null )
            throw new ItemNotFoundException( x.toString( ) );
        if( x.compareTo( (T) t.element ) < 0 )
            t.setLeft(remove( x, t.getLeft() ));
        else if( x.compareTo( (T) t.element ) > 0 )
            t.right = remove( x, t.right );
        else if( t.getLeft() != null && t.right != null ) 
        {
            t.element = findMin( t.right ).element;
            t.right = removeMin( t.right );
        } else
            t = ( t.getLeft() != null ) ? t.getLeft() : t.right;
        return t;
    }
   
    protected BinaryNode<T> removeMin( BinaryNode <T>t ) {
        if( t == null )
            throw new ItemNotFoundException( );
        else if( t.getLeft() != null ) {
            t.setLeft(removeMin( t.getLeft() ));
            return t;
        } else
            return t.right;
    }
    
    
    protected BinaryNode<T> findMin( BinaryNode <T>t ) {
        if( t != null )
            while( t.getLeft() != null )
                t = t.getLeft();
        
        return t;
    }
   
    private BinaryNode<T> findMax( BinaryNode <T>t ) {
        if( t != null )
            while( t.right != null )
                t = t.right;
        
        return t;
    }
    
    @SuppressWarnings("unchecked")
    private BinaryNode<T> find( Comparable <T>x, BinaryNode <T>t ) {
        while( t != null ) {
            if( x.compareTo( (T) t.element ) < 0 )
                t = t.getLeft();
            else if( x.compareTo( (T) t.element ) > 0 )
                t = t.right;
            else
                return t;    
        }
        
        return null;        
    }
    
}

